#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
const int N = 1000;
int a[] = {5,3,6,2,1,4,8,7};
void insert_sort(int a[],int len){
	for(int i = 1 ; i < len ; i++){//j是新插的数从哪个位置开始往前对比
		int key = a[i];//key是新插的数
		int j = i-1;//j是在key需要插的位置之前的最大的数的位置
		while(j >= 0&&a[j] > key){//由于是从小到大插入的，因此a【j】一定是位于即将插入值之前并且除了即将插入的值之外最大的一个，如果a【j】更小那么说明一定没有比新加入的大的，因此可以直接跳出循环
			a[j+1] = a[j];//新的不如它前面最大的，就不要占着后面的位置
			j = j-1;//对比完一个再找前面第二大的
		}
		a[j+1]=key;//ok终于找到比key小的，那key就放在这个key之前最大的数后面
	}
} 
int main(){
	int n = sizeof(a)/sizeof(a[0]);
	printf("插入排序前数组: ");
	for(int i = 0 ; i < n ; i++){
		cout <<  a[i] << " ";
	}
	printf("\n插入排序后数组: ");
	insert_sort(a,n);
	for(int i = 0 ; i < n ; i++){
		cout <<  a[i] << " ";
	}
	
	return 0;
}
